#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // simple method
    //  vector<int> partitionLabels(string s)
    //  {
    //      int letter_end[26] = {-1};
    //      for (size_t i = 0; i < s.size(); i++)
    //      {
    //          letter_end[s[i] - 'a'] = i;
    //      }
    //      vector<int> res;
    //      int start = 0;
    //      int end = 0;
    //      for (int i = 0; i < (int)s.size(); i++)
    //      {
    //          end = max(letter_end[s[i] - 'a'], end);
    //          if (end == i)
    //          {
    //              res.push_back(end - start + 1);
    //              start = end + 1;
    //          }
    //      }
    //      return res;
    //  }

    // complex method
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[0] < b[0];
    }
    vector<vector<int>> cal(string &s)
    {
        vector<vector<int>> all_res(26, vector<int>(2, INT_MIN));
        for (size_t i = 0; i < s.size(); i++)
        {
            if (all_res[s[i] - 'a'][0] == INT_MIN)
            {
                all_res[s[i] - 'a'][0] = i;
            }
            all_res[s[i] - 'a'][1] = i;
        }
        vector<vector<int>> filter_vec;
        for (size_t i = 0; i < all_res.size(); i++)
        {
            if (all_res[i][0] != INT_MIN)
            {
                filter_vec.push_back(all_res[i]);
            }
        }
        return filter_vec;
    }
    vector<int> partitionLabels(string s)
    {
        vector<vector<int>> section = cal(s);
        sort(section.begin(), section.end(), cmp);
        int left_board = 0;
        int right_board = section[0][1];
        vector<int> res;
        for (size_t i = 1; i < section.size(); i++)
        {
            if (section[i][0] > right_board)
            {
                res.push_back(right_board - left_board + 1);
                left_board = section[i][0];
            }
            right_board = max(right_board, section[i][1]);
        }
        res.push_back(right_board - left_board + 1);
        return res;
    }
};

int main()
{
    string s{"ababcbacadefegdehijhklij"};
    Solution sol;
    vector<int> res = sol.partitionLabels(s);
    for (auto num : res)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}